package cn.lishiyuan.algorithm.list;


import java.util.Objects;
import java.util.Random;

/**
 * 跳表
 *
 * head
 *  ↓
 * head ——————>  5
 *  ↓            ↓
 * head -> 1 ->  5  -> 10
 *  ↓      ↓     ↓      ↓
 * head -> 1->4->5->6->10
 *
 */

public class SkipList<T extends Comparable<T>> {
    // 最多32层
    public static final int MAX_LEVEL = (32 - 1);

    Node<T> head = null;

    private int size = 0;

    private Random random = new Random();

    public final static class Node<T extends Comparable<T>>{
        T data;
        // 层级
        LevelInfo<T>[] levelInfos;

        public final static class LevelInfo<T extends Comparable<T>>{
            // 同层上一个元素
            Node<T> prev = null;
            // 同层的下一个元素
            Node<T> next = null;
            // 下一层元素
            Node<T> down = null;
        }
    }

    public SkipList(){
        size = 0;
        // 首节点
        head = newNode(MAX_LEVEL, null);
    }

    public void add(T data) {
        if(Objects.isNull(data)){
            throw new IllegalArgumentException("不能为空");
        }

        int level = randomLevel();
        Node<T> node = newNode(level,data);
        Node<T> prev = head;

        // 循环插入节点
        for(int i = level;i >= 0; i--){

            // 查询每一层的节点查找第一个大于当前元素的node
            while (prev.levelInfos[i].next != null && prev.levelInfos[i].next.data.compareTo(data) <= 0){
                // 继续向后查找
                prev = prev.levelInfos[i].next;
            }
            // 当前元素的下个元素就是下个元素
            node.levelInfos[i].next = prev.levelInfos[i].next;
            node.levelInfos[i].prev = prev;

            // 下个元素是当前元素
            if(prev.levelInfos[i].next != null){
                prev.levelInfos[i].next.levelInfos[i].prev = node;
            }
            prev.levelInfos[i].next = node;

        }

        size++;
    }

    public T remove(T data) {
        if(Objects.isNull(data)){
            throw new IllegalArgumentException("不能为空");
        }

        if(isEmpty()){
            return null;
        }

        Node<T> node = findNode(data);
        if(node == null){
            return null;
        }

        for (int i = node.levelInfos.length - 1; i >= 0; i--) {
            // 本层元素的上一个元素
            Node<T> prev = node.levelInfos[i].prev;
            prev.levelInfos[i].next = node.levelInfos[i].next;
            if(node.levelInfos[i].next != null){
                // 本层元素的下个元素的上个元素是当前元素的上个元素
                node.levelInfos[i].next.levelInfos[i].prev = prev;
            }

            // 垃圾回收
            node.levelInfos[i].next = null;
            node.levelInfos[i].prev = null;
        }

        size--;

        return node.data;
    }

    public T search(T data) {
        if(Objects.isNull(data)){
            throw new IllegalArgumentException("不能为空");
        }
        Node<T> node = findNode(data);
        return node!=null ? node.data : null;
    }

    public boolean contains(T data){
        if(Objects.isNull(data)){
            throw new IllegalArgumentException("不能为空");
        }
        Node<T> node = findNode(data);
        return node != null;
    }


    private Node<T> findNode(T data){
        if(isEmpty()){
            return null;
        }
        int i = MAX_LEVEL;

        Node<T> now = head;
        // 查询每一层的节点查找第一个大于当前元素的node
        while (now != null){
            // 头节点
            if(now.data==null){
                if(now.levelInfos[i].next == null || now.levelInfos[i].next.data.compareTo(data) > 0){
                    // 向下
                    now = now.levelInfos[i].down;
                    i--;
                }else{
                    // 向右
                    now = now.levelInfos[i].next;
                }
                continue;
            }

            if(now.data.compareTo(data) == 0){
                // 如果当前元素等于元素则直接返回
                return now;
            }else if(now.data.compareTo(data) < 0 && (now.levelInfos[i].next== null || now.levelInfos[i].next.data.compareTo(data) > 0)){
                // 如果当前元素的next为null 或者next大于当前元素则向下查找
                now = now.levelInfos[i].down;
                i--;
            }else if(now.data.compareTo(data) < 0 && (now.levelInfos[i].next.data.compareTo(data) <= 0)){
                // 如果当前元素小于目标元素，下个元素小于目标i元素则走向下个元素
                now = now.levelInfos[i].next;
            }
//            else {
//                // 当前元素大于目标，则没有找到，这种情况不可能发生
//                return null;
//            }
        }
        return null;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    // 构建节点
    private Node<T> newNode(int level, T data){
        Node<T> node = new Node<>();
        node.data = data;
        node.levelInfos = new Node.LevelInfo[level+1];

        Node<T> downNode = null;
        for (int i = 0; i <= level; i++) {
            Node.LevelInfo<T> levelInfo = new Node.LevelInfo<T>();
            levelInfo.down = downNode;
            node.levelInfos[i] = levelInfo;
            downNode = node;
        }

        return node;
    }

    private static final double P = 0.25;

    /**
     * 生成符合幂次定理的level
     * @return
     */
    private int randomLevel() {
        int level = 0;
        // 每次只有四分之一的机会加一
        while (random.nextDouble() < P)
            level += 1;
        return Math.min(level, MAX_LEVEL);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = MAX_LEVEL; i >= 0; i--) {
            Node<T> node = head;
            while (node != null) {
                sb.append("--> ").append(node.data).append(" ");
                node = node.levelInfos[i].next;
            }
            sb.append("\n");
        }

        return sb.toString();
    }
}
